package algorithm.sort;

import java.util.Arrays;

/**
 * @ Author     ：wangyw
 * @ Date       ：Created in 下午5:38 2021/11/2
 * @ Description：归并排序迭代实现
 */
public class _04MergeSort_1 implements SortAlgrithm {

    @Override
    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
        int ms = 1;
        int n = unsorted.length;
        while (ms < n) {
            int l = 0;
            while (l < n) {
                if (l + ms >= n) {
                    break;
                }
                int m = l + ms - 1;
                int r = Math.min(m + ms, n - 1);
                _04MergeSort.merge(unsorted, l, m, r);
                l = r + 1;
            }
            if (ms > n >> 1) {
                break;
            }
            ms <<= 1;
        }
        return unsorted;
    }

    public static void main(String[] args) {
        Integer[] randomIntArr = SortUtils.getRandomIntArr(15, 100);
        System.out.println(Arrays.toString(randomIntArr));
        new _04MergeSort_1().sort(randomIntArr);
        System.out.println(Arrays.toString(randomIntArr));
    }
}
